#include "heap1.h"
#include <stdlib.h>
#include "../logger/logger.h"
PriorityQueue Initialize(int MaxElements)
{
    PriorityQueue H;
    if (MaxElements < MinPQSize)
        Error("Priority queue size is too small");
    H = malloc(sizeof(*H));
    if (!H)
        FatalError("Out of space!");
    H->Elements = malloc((MaxElements + 1) * sizeof(*(H->Elements)));
    if (!H->Elements)
        FatalError("Out of space!");
    H->Capacity = MaxElements;
    H->Size = 0;
    H->Elements[0] = MinData;
    return H;
}

void Destory(PriorityQueue H)
{
    if (H)
    {
        free(H->Elements);
        free(H);
    }
}

void MakeEmpty(PriorityQueue H)
{
    H->Size = 0;
}

ElementType FindMin(PriorityQueue H)
{
    if (IsEmpty(H))
        FatalError("Heap is empty");
    return H->Elements[1];
}

int IsEmpty(PriorityQueue H)
{
    return H->Size == 0;
}

int IsFull(PriorityQueue H)
{
    return H->Capacity == H->Size;
}

void Insert(ElementType x, PriorityQueue H)
{
    //i是空穴的位置
    int i;
    if (IsFull(H))
        FatalError("Priority queue is full");
    for (i = ++H->Size; x < H->Elements[i / 2]; i /= 2)
        H->Elements[i] = H->Elements[i / 2];
    H->Elements[i] = x;
}

ElementType DeleteMin(PriorityQueue H)
{
    int i, Child;
    ElementType MinElement, LastElement;
    if (IsEmpty(H))
        FatalError("Priority queue is empty");
    MinElement = H->Elements[1];
    LastElement = H->Elements[H->Size--];

    for (i = 1; i * 2 < H->Size; i = Child)
    {
        Child = i * 2;
        //Child有兄弟节点
        if (Child != H->Size && H->Elements[Child] > H->Elements[Child + 1])
            Child++;
        if (LastElement > H->Elements[Child])
            H->Elements[i] = H->Elements[Child];
        else
            break;
    }
    H->Elements[i] = LastElement;
    return MinElement;
}